package problems;

import lib.MillerRabin32;


public class Euler058 extends AbstractEuler {

	@Override
	public Number calculate() {
		//subsequent values for each diagonal for side lengths 1, 3, 5, 7, 9 are:
		//top right: 1, 3, 13, 31, 57
		//			 (+2,+10,+18,+26)
		//			  ((+8, +8, +8))
		//top left: 1, 5, 17, 37, 65 (+4, +12, +20, +28 (+8, + 8, +8))
		//bottom left: 1, 7, 21, 43, 73 (+6, +14, +22, +30 (+8, + 8, +8))
		//bottom right: 1, 9, 25, 49, 81 (+8, +16, + 24, +32 (+8, + 8, +8))
		
		//definitions: side length 1 = layer 0, side length 3 = layer 1, side length 5 = layer 2, etc.
		//so, layer = (side length - 1)/2, and side length = 2 * layer + 1.

		//BR is squares of odd numbers.
		//Difference with BL is: 0, 2, 4, 6, 8
		//Difference with TL is: 0, 4, 8, 12
		//Difference with TR is: 0, 6, 12, 18

		//in other words, the value on each diagonal is the square of its side length, minus (layer * 2 * (quadrants away from BR, clockwise)). 
		//that's it for theory, let's do some calculations!
		
		int layer, primesFound;
		for (layer = 2, primesFound = 3; primesFound / (4 * layer + 1.0) >= 0.1; layer++) {
			int br = (2 * layer + 1); br *= br;
			int bl = br - 2 * layer;
			int tl = bl - 2 * layer;
			int tr = tl - 2 * layer;

			if (MillerRabin32.isPrime(bl)) primesFound++;
			if (MillerRabin32.isPrime(tl)) primesFound++;
			if (MillerRabin32.isPrime(tr)) primesFound++;
		}
		
		return 2 * layer + 1;
	}

	@Override
	protected Number getCorrectAnswer() {
		return 26241;
	}

}
